10776. Определить комбинацию

Напечатать все разные r-комбинации строки s (r-комбинациею строки s называется набор из r символов строки s). Если одни и те же r символов дают разные комбинации, то печатать следует лишь ту одну, в которой символы расположены в алфавитном порядке. Строка s содержит только буквы нижнего регистра. Буквы в строке могут повторяться.

Вход. Входные данные состоят из нескольких тестов. Каждый тест в одной строке содержит строку s длиной от 1 до 30 символов и число r (0 < r £ длина(s))

Выход. Для каждого теста вывести все разные r-комбинации строки s в алфавитном порядке. Каждую комбинацию выводить в отдельной строке. Для каждого теста существует не более 1000 разных r-комбинаций.

Пример входа

abcde 2

abcd 3

aba 2

Пример выхода

ab

ac

ad

ae

bc

bd

be

cd

ce

de

abc

abd

acd

bcd

aa

ab

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Отсортируем символы строки s в алфавитном порядке. Пусть s = s₁s₂…s_n. Организуем перебор всех разных неповторяющихся подпоследовательностей … . Количество таких подпоследовательностей в общем случае пропорционально O(2ⁿ), где n – длина строки s. Но по условию задачи сказано, что для каждого входного теста количество искомых подпоследовательностей не более 1000.

Пример

Рассмотрим входные данные для третьего теста. Отсортированная строка s имеет вид: aab. Существует = 3 возможных комбинаций из двух символов: первый и второй символы (aa), первый и третий символы (ab), второй и третий символы (ab). Но разными будут лишь две комбинации, которые выводим в алфавитном порядке: aa, ab.

Реализация алгоритма

Сортировку входной строки можно осуществить при помощи функции qsort библиотеки stdlib.h. Функция – компаратор compare, которая сравнивает два символа, имеет вид:

int compare(const void *a, const void *b)

{

return *(char *)a - *(char *)b;

}

Обозначим через len длину строки s. Строка s хранится в массиве символов char s[31] (длина строки 30 символов плюс один байт для символа 0 в конце строки). Массив char p[31] будет содержать текущую сгенерированную искомую подпоследовательность … . Ввод и обработка тестов осуществляется в цикле

while(scanf("%s %d",&s,&r) == 2)

{

len = strlen(s);

qsort(s,len,sizeof(char),compare);

doit(0,0);

}

Функция void doit(int pos,int depth) генерирует все разные подпоследовательности … длины r - depth, где индекс первого элемента не меньше чем pos: ³ pos. Номер индекса массива s начинается с нуля, поэтому вызов функции doit(0,0) сгенерирует все искомые подпоследовательности … для текущего теста (Если положить depth = 0, pos = 0, то как раз получим все подпоследовательности … , где ³ 0). Для индекса первого элемента последовательности … следует перебрать весь промежуток pos £ £ len – (r - depth), для которых значения разные, так как после элемента должно еще следовать как минимум r – depth - 1 элементов. После того как первый элемент выберется, следует построить все различные подпоследовательности … , где > .

void doit(int pos,int depth)

{

int i;

if (depth == r) print(); else

for(i = pos; i <= len + depth - r;)

{

p[depth] = s[i];

doit(i+1,depth+1);

i++; while(s[i] == s[i-1]) i++;

}

}

Функция печати очередной подпоследовательности print() имеет вид:

void print(void)

{

int i;

for(i = 0; i < r; i++)

printf("%c",p[i]);

printf("\n");

}